Теорема Рабина-Скотта

Для любого НКА существует ДКА, распознающий тот же самый язык.

Возьмем произвольный НКА $\mathcal{B} = (Q, \Sigma, \delta, S, T)$. Построим ДКА $\mathcal{A}$ такой, что $L(\mathcal{A}) = L(\mathcal{B})$. Пусть $\mathcal{A} = (2^Q, \Sigma, \delta', S, T')$, где $\delta'(P, a) = \delta(P, a)$, $T' = \{P \in 2^Q \mid P \cap T \neq \varnothing\}$. Докажем, что $\delta'(P, w) = \delta(P, w)$ для любого слова $w$ индукцией по $|w|$: **База индукции**: для $|w| = 0$ имеем $\delta'(P, \lambda) = \delta(P, \lambda) = P$. **Шаг индукции**: пусть $w = ua$, $a \in \Sigma$. $$ \delta'(P, w) = \delta'(\delta'(P, u), a) = \delta'(\delta(P, u), a) = \delta(\delta(P, u), a) = \bigcup_{r \in \delta(P, u)} \delta(r, a) = \bigcup_{q \in P} \delta(q, ua) = \delta(P, ua) $$ Осталось заметить, что $$ L(\mathcal{A}) = \{w \in \Sigma^* \mid \delta'(S, w) \in T'\} = \{w \in \Sigma^* \mid \delta'(S, w) \cap T \neq \varnothing\} = \{w \in \Sigma^* \mid \delta(S, w) \cap T \neq \varnothing\} = L(\mathcal{B}) $$ $\square$